package practise.alogrithm.hundredInterviewQuestions;

import java.util.ArrayList;
import java.util.List;

/**
 * in a array, only two numbers that appear once, while others appear twice, find the two number.
 */
public class TwoUniqueNumber {
    public static List<Integer> findMumber(int[] arrays){
        int mask = 0;
        int ONE = 1;
        int TOKEN = 0;
        int number1=0,number2=0;
        List<Integer> result = new ArrayList<>(2);
        List<Integer> array1 = new ArrayList<>(arrays.length/2+1);
        List<Integer> array2 = new ArrayList<>(arrays.length/2+1);
        for(int i : arrays){
            mask = mask^i;
        }
        for(int i=0;i<32;i++){
            if(((ONE<<i)&mask)!=0){
                TOKEN = ONE<<i;
                break;
            }
        }
        for(int i : arrays){
            if((i&TOKEN)==0){
                array1.add(i);
            }
            else {
                array2.add(i);
            }
        }

        for(int i : array1){
            number1 = number1^i;
        }
        result.add(number1);
        for(int i : array2){
            number2 = number2^i;
        }
        result.add(number2);
        return result;
    }

    public static void main(String[] args){
        System.out.print("Result:"+findMumber(new int[]{1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,9}));
    }
}
